/*
 * @Author: your name
 * @Date: 2024-04-17 10:04:53
 * @LastEditTime: 2024-04-17 10:14:38
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\347.前-k-个高频元素.cpp
 */
/*
 * @lc app=leetcode.cn id=347 lang=cpp
 *
 * [347] 前 K 个高频元素
 */

// @lc code=start
class Solution {
public:
    // 小顶堆
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };

    
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 先统计频次
        unordered_map<int, int> maps;
        for(int num:nums){
            maps[num]++;
        }
        // 定义一个小顶堆，大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
        for(auto it = maps.begin(); it != maps.end(); it++){
            pri_que.push(*it);
            if(pri_que.size() > k){
                pri_que.pop();
            }

        }
        // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
        vector<int >res(k);
        for(int i = k-1;i>=0; i--){
            res[i] = pri_que.top().first;
            pri_que.pop();
        }
        return res;
    }
};
// @lc code=end

// 重要